package datastructure.tree;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-30
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] array = new int[]{5, 1, 9, -1, 4, 10};
        long startTime = System.currentTimeMillis();
        heapSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println(Arrays.toString(array));
        System.out.println("耗时：" + (endTime - startTime));
    }

    /**
     * 构建堆
     *
     * @param array
     */
    private static void heapSort(int[] array) {

        // 非叶子结点
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            adjustHeap(array, i, array.length);
        }

        for (int j = array.length - 1; j > 0; j--) {
            // 将堆顶元素与末尾元素进行交换
            int temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            adjustHeap(array, 0, j);
        }
    }

    /**
     * 调整堆
     *
     * @param array  待排序数组
     * @param i      父节点
     * @param length
     */
    private static void adjustHeap(int[] array, int i, int length) {
        int temp = array[i];
        // 左孩子
        int lChild = 2 * i + 1;
        while (lChild < length) {
            // 右孩子
            int rChild = lChild + 1;
            if (rChild < length && array[lChild] < array[rChild]) {
                // 如果右孩子的值大于左孩子值，则选取右孩子
                lChild++;
            }

            // 父结点值大于 左右孩子结点 不用交换直接退出
            if (temp > array[lChild]) {
                break;
            }

            // 交换
            array[i] = array[lChild];

            // 选取孩子结点的左孩子结点，继续向下筛选
            i = lChild;
            lChild = 2 * i + 1;
        }
        // 交换
        array[i] = temp;
    }
}
